const P_FACTOR = 0.25
const MAX_LEVEL = 32

class Node {
  constructor(val, maxLevel) {
    this.val = val
    this.next = new Array(maxLevel).fill(0)
  }
}

const randomLevel = () => {
  let lv = 1
  /* 随机生成 lv */
  while (Math.random() < P_FACTOR && lv < MAX_LEVEL) {
    lv++
  }
  return lv
}

var Skiplist = function () {
  this.level = 0
  this.head = new Node(-1, MAX_LEVEL)
}

// 找出第i层小于targer的最大节点
Skiplist.prototype.find = function (target, afterWhileFn) {
  let curr = this.head
  for (let i = this.level - 1; i >= 0; i--) {
    while (curr.next[i] && curr.next[i].val < target) {
      curr = curr.next[i]
    }
    if (typeof afterWhileFn === 'function') {
      afterWhileFn.bind(this)(i, curr)
    }
  }
  return curr
}

/**
 * @param {number} target
 * @return {boolean}
 */
Skiplist.prototype.search = function (target) {
  let curr = this.find(target)
  curr = curr.next[0]

  return curr && curr.val === target
}

/**
 * @param {number} num
 * @return {void}
 */
Skiplist.prototype.add = function (num) {
  const update = new Array(MAX_LEVEL).fill(this.head)
  this.find(num, (i, c) => {
    update[i] = c
  })
  const level = randomLevel()
  this.level = Math.max(this.level, level)
  const newNode = new Node(num, level)
  for (let i = 0; i < level; i++) {
    /* 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点 */
    newNode.next[i] = update[i].next[i]
    update[i].next[i] = newNode
  }
}

/**
 * @param {number} num
 * @return {boolean}
 */
Skiplist.prototype.erase = function (num) {
  const update = new Array(MAX_LEVEL).fill(0)
  let curr = this.find(num, (i, c) => {
    update[i] = c
  })
  // console.log('cur', curr)
  curr = curr.next[0]
  /* 如果值不在存则返回 false */
  if (!curr || curr.val !== num) return false
  for (let i = 0; i < this.level; i++) {
    if (update[i].next[i] !== curr) break
    /* 对第 i 层的状态进行更新，将 next 指向被删除节点的下一跳 */
    update[i].next[i] = curr.next[i]
  }
  /* 更新当前的 level */
  while (this.level > 1 && !this.head.next[this.level - 1]) {
    this.level--
  }
  return true
}

/**
 * Your Skiplist object will be instantiated and called as such:
 * var obj = new Skiplist()
 * var param_1 = obj.search(target)
 * obj.add(num)
 * var param_3 = obj.erase(num)
 */
